package leetcode_1000;

/**
 *@author 周杨
 *NumbersAtMostNGivenDigitSet_902_ 给定一个排序的数组 里面出现不重复的1-9 问用这些数字能组成多少数字不超过N
 *describe:用动态规划 
 *2018年11月13日 下午8:57:25
 */
public class NumbersAtMostNGivenDigitSet_902_ {
	public int atMostNGivenDigitSet(String[] D, int N) {
		int []toint=new int[D.length];//保存D中的数字 是升序
		for(int i=0;i<D.length;++i) {
			toint[i]=Integer.valueOf(D[i]);
		}
		String S = String.valueOf(N);
        int K = S.length();
        int[] dp = new int[K+1];//dp[i]的位置 是k位处的最优解
        dp[K] = 1;//储存最后一个值1
        for (int i = K-1; i >= 0; --i) {//开始计算dp[i] 从N的长度往前算
            int Si = S.charAt(i) - '0';//转换成数字
            for (int now: toint) {
                if (now < Si)//如果小于 当前位置的组合数就加上D长度的一个次幂
                    dp[i] += Math.pow(D.length, K-i-1);
                else if (now == Si)//相等就加上一个位置的组合数
                    dp[i] += dp[i+1];
                //剩下的不必计算
            }
        }

        for (int i = 1; i < K; ++i)
            dp[0] += Math.pow(D.length, i);
        return dp[0];
    }
}
